大数据算法(2025年春季)


助教:王运韬 wangyuntao@mail.ustc.edu.cn ,王向禄 wz124517@mail.ustc.edu.cn,莫官霖 moguanlin@mail.ustc.edu.cn ,张嘉贤 zjx20200@mail.ustc.edu.cn


课程简介


       算法与理论是计算机科学的核心领域之一。随着大数据时代的来临,传统的算法理论已经不能很好地解决人工智能、 物联网、工业制造等领域所遇到的实际问题。本门课程主要介绍基于大数据的新型算法技术,如随机采样、数据降维、数据压缩、分布式计算、 流数据计算、聚类、分类、随机优化等,以及相关的理论和数学技巧,如概率计算方法、vc维、通信复杂度、机器学习、深度学习理论等。 作为一门理论方向课程,帮助学生掌握解决大数据问题所需的理论和算法工具,为相关领域的工程实践打好基础。


数学工具

  1. 基础数学和统计工具 (pdf)
  2. 集中不等式、Chaining (pdf)

随机算法

  1. 随机算法——Maxcut (pdf)
  2. EX.Balls and Bins (pdf)
  3. K-means 聚类 (pdf)
  4. Karger 算法 (pdf)

降维

  1. 主成分分析 (pdf)
  2. JL 变换 (pdf)
  3. JL 变换的应用 (pdf)
  4. JL 变换的应用(线性变换) (pdf)
  5. 多维尺度分析 (pdf)

近邻查询

  1. 局部敏感哈希 (pdf)
  2. 乘积量化 (pdf)

次线性算法

  1. 1-median 问题 (pdf)
  2. 平均距离问题 (pdf)
  3. k-median 问题 (pdf)

VC 维与核心集

  1. VC维简介 (pdf)
  2. VC维与PAC学习 (pptx)
  3. 核心集 (pdf)
  4. 核心集:深度学习 (pdf)

最优传输

  1. Sinkhorn算法简介 (pdf)
  2. 最优传输问题:理论与应用 (pdf)

分布式算法

  1. 重心估计 (pdf)
  2. 分布式算法综述 (pptx)

Beyond worst case analysis

  1. k-means问题 (pdf)
  2. 压缩感知 (pdf)
Top